import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class TreeTest {

    public static void main(String[] args) {

//        int[] preOrder = {10, 6, 4, 8, 14, 12, 16};
//        int[] inOrder = {4, 6, 8, 10, 12, 14, 16};

        int[] preOrder = new int[]{1, 2, 4, 7, 3, 5, 6, 8};
        int[] inOrder = new int[]{4, 7, 2, 1, 5, 3, 8, 6};
        testTree(preOrder, inOrder);


    }


    public static void testTree(int[] preOrder, int[] inOrder) {

        try {
            BinaryTreeNode treeNode = buildTree(preOrder, inOrder);
            if (treeNode == null) {
                System.out.println("treeNode: null");
                return;
            }

            // TODO: 2019/10/18 打印完整二叉树 
            BinaryTreeNode tmpNode = treeNode;
            System.out.println("treeNode: ");
            while (tmpNode != null) {
                System.out.println(tmpNode.value + "  ");
                tmpNode = tmpNode.mLeft;
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    /**
     * 二叉树结构
     */
    static class BinaryTreeNode {
        int value;
        BinaryTreeNode mLeft;
        BinaryTreeNode mRight;
    }

    /**
     * 根据前序遍历序列和中序遍历序列重构二叉树
     * 剑指offer 面试题7 java版本实现
     * @param preOrder  前序遍历序列
     * @param inOrder   序遍历序列
     * @return  根节点
     * @throws Exception
     */
    private static BinaryTreeNode buildTree(int[] preOrder, int[] inOrder) throws Exception {

        if (preOrder.length != inOrder.length)
            throw new Exception("数据异常，长度不一致");
        if (preOrder.length == 0)
            return null;
        BinaryTreeNode rootNode = new BinaryTreeNode();

        rootNode.value = preOrder[0];
        rootNode.mLeft = rootNode.mRight = null;

        if (preOrder.length == 1) {
            if (preOrder[0] != inOrder[0]) {
                throw new Exception("数据异常");
            }

            System.out.println("find leafNode: " + rootNode.value);
            System.out.println("-------------- ");
            return rootNode;
        }

        int leftLength = 0;
        int rightLength = 0;
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootNode.value) {
                leftLength = i;
                break;
            }
        }
        rightLength = inOrder.length - leftLength - 1;
        if (leftLength > 0) {
            int[] leftPreOrder = Arrays.copyOfRange(preOrder, 1, leftLength + 1);
            int[] leftInOrder = Arrays.copyOfRange(inOrder, 0, leftLength);
            System.out.println("leftPreOrder : " + Arrays.toString(leftPreOrder));
            System.out.println("leftInOrder : " + Arrays.toString(leftInOrder));
            BinaryTreeNode leftRootNode = buildTree(leftPreOrder, leftInOrder);
            rootNode.mLeft = leftRootNode;
        }

        if (rightLength > 0) {
            int[] rightPreOrder = Arrays.copyOfRange(preOrder, leftLength + 1, preOrder.length);
            int[] rightInOrder = Arrays.copyOfRange(inOrder, leftLength + 1, inOrder.length);

            System.out.println("rightPreOrder : " + Arrays.toString(rightPreOrder));
            System.out.println("rightInOrder : " + Arrays.toString(rightInOrder));
            BinaryTreeNode rightRootNode = buildTree(rightPreOrder, rightInOrder);
            rootNode.mRight = rightRootNode;
        }

        return rootNode;
    }


}
